1. Technical Field
The present invention relates in general to a method and system for data processing and in particular to a method and system for controlling access to a shared resource in a data processing system. Still more particularly, the present invention relates to a method and system for controlling access to a shared resource by a plurality of requesters in a data processing system, wherein at least a highest priority is assigned to one of the plurality of requesters substantially randomly with respect to previous priorities of the plurality of requesters.
2. Description of the Related Art
In data processing systems, it is common for a single resource to be shared by multiple devices that request service from or access to the resource. In these instances, some method of controlling access to the resource must be implemented to ensure that the devices obtain access to the shared resource in an manner that promotes efficient operation of the data processing system.
In conventional data processing systems, regulating access to a shared resource is often accomplished by assigning a fixed priority to each of the devices that may request service from or access to the shared resource. Such fixed priority systems, while providing a simple and efficient method of determining which access requests to grant, often fail to allocate adequate access to lower priority devices and operations, particularly when high priority devices generate frequent access requests. In order to address this problem, some conventional data processing systems implement a "round robin" resource allocation scheme in which access to the shared resource is provided to each of the multiple devices sequentially and cyclically. However, the implementation of a round robin resource allocation mechanism has its own concomitant problems. First, high priority devices and operations can be delayed, producing latency in critical timing paths and diminishing overall system performance. Second, and more subtlety, empirical data indicates that deterministic methods of allocating resource access, such as round robin, can lead to "live locks" or situations in which request timings permit only a few processes or devices to gain access to a shared resource, while effectively preventing access to the shared resource by other processes or devices.
As should thus be apparent, it would be desirable to provide an improved method and system for controlling access to a shared resource within a data processing system. In particular, it would be desirable to provide a method and system for controlling access to a shared resource that permit both high priority and low priority devices adequate access to a shared resource. In addition, it would be desirable to minimize the request to grant latency. Furthermore, in order to minimize live locks, it would be desirable for the method and system for controlling access to the shared resource to operate in a substantially non-deterministic manner.